Obeleži sve kategorije koje odgovaraju problemu

Елементи целобројне матрице $A_{m\times n}$ су савијени у цилиндар тако да се горња и доња (прва и последња) врста матрице додирују. Ако се робот креће са левог краја цилиндра (од прве колоне) ка десном (до последње колоне), уз дозвољена кретања једно поље горе-десно, десно, доле-десно, одредити пут којим робот може да прође да би обезбедио најмањи збир вредности поља на том путу.

Улаз

У првој линији стандардног улаза уноси се број редова табеле $m$ ($1 \le m \le 30$), у другој број колона табеле $n$ ($1 \le n \le 30$), а у следећих $m$ редова по $n$ вредности од 0 до 100.

Излаз

На стандардном излазу у првој линији приказати тражену вредност минималног збира, а у следећих $m$ редова индекс врсте и колоне (раздвојене празнином) поља преко којих пролази робот. Ако постоји више путева минималног збира, исписати било који од њих.

Пример

Улаз

5
6
4 3 5 7 5 8
1 9 4 1 3 9
2 3 9 1 2 5
1 7 8 2 0 1
4 6 1 9 1 7

Излаз

8
1 0
0 1
4 2
3 3
3 4
3 5

Објашњење

Робот прелази преко следећих поља (прелаз са поља (0, 1) на поље (4, 2) могућ је захваљујући цилиндричном облику матрице):

. 3 . . . .
1 .
. . . . . .
. . . 2 0 1
. . 1 . . .